//给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。 
//
// 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。 
//
// 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 
//
// 
//
// 示例： 
//
// 
//输入：[[1,2], [2,3], [3,4]]
//输出：2
//解释：最长的数对链是 [1,2] -> [3,4]
// 
//
// 
//
// 提示： 
//
// 
// 给出数对的个数在 [1, 1000] 范围内。 
// 
// Related Topics 贪心 数组 动态规划 排序 
// 👍 199 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class MaximumLengthOfPairChain {
    public static void main(String[] args) {
        int[][] pairs = {{7,9},{4,5},{7,9},{-7,-1},{0,10},{3,10},{3,6},{2,3}};
        new MaximumLengthOfPairChain().new Solution().findLongestChain(pairs);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 尝试使用map存储每一个链：失败（添加时会被短链堵住了）
     * 和之前的dp一样，dp[i]存放的是以paris[i][1]结尾的最大长度
     * 必须将原始数组进行排序才能继续操作
     *
     * 可以对原属数组进行二维升序，一次遍历得到结果
     */
    class Solution {
        public int findLongestChain(int[][] pairs) {
            int len = pairs.length;
            if (len == 1) return len;
            int res = 1;
            Arrays.sort(pairs,(a,b)->{ return a[1]-b[1]; });//TODO 这里是二维升序，妙啊
            int tail = pairs[0][1];
            for (int i = 1; i < len; i++) {
                if (pairs[i][0]>tail){
                    res++;
                    tail = pairs[i][1];
                }
            }
            /*
            //使用DP的方式
            int[] dp = new int[len];
            Arrays.fill(dp, 1);
            Arrays.sort(pairs,(a,b)->{ return a[0]-b[0]; });//TODO 这里是一维升序，这样才能向前遍历
            for (int i = 1; i < len ; i++) {
                for (int j = 0; j < i ; j++) {
                    if (pairs[i][0]>pairs[j][1]){
                        dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                }
                res = Math.max(res, dp[i]);
            }*/

            //可以对排序过后的数组一次遍历即可得到结果

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}